package day05;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/5 20:52
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一棵二叉树，请按以下要求的顺序收集它的全部节点：
 *
 * 依次从左到右，每次收集并删除所有的叶子节点
 * 重复如上过程直到整棵树为空
 *
 *
 * 示例:
 *
 * 输入: [1,2,3,4,5]
 *
 *           1
 *          / \
 *         2   3
 *        / \
 *       4   5
 *
 * 输出: [[4,5,3],[2],[1]]
 *
 *
 * 解释:
 *
 * 1. 删除叶子节点 [4,5,3] ，得到如下树结构：
 *
 *           1
 *          /
 *         2
 *
 *
 * 2. 现在删去叶子节点 [2] ，得到如下树结构：
 *
 *           1
 *
 *
 * 3. 现在删去叶子节点 [1] ，得到空树：
 *
 *           []
 */
public class Solution3 {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> resList = new ArrayList<>();
        while(root != null){
            List list = new ArrayList<>();
            root = recur(root, list);
            resList.add(list);
        }
        return resList;
    }
    private TreeNode recur(TreeNode root, List<Integer> list){
        if(root == null){
            return null;
        }
        if(root.left == null && root.right == null){
            list.add(root.val);
            return null;
        }
        root.left = recur(root.left, list);
        root.right = recur(root.right, list);
        return root;
    }
}
